package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;

/**
 *   1
 *  / \
 * 2  4
 *   /
 *  3
 *
 * LCA(1, 2, 3) 递归之后 => 2 和 3 返回 1
 *   LCA(2, 2, 3)
 *     2
 *   LCA(4, 2, 3) 递归之后 => 3 和 NULL 返回 3
 *     LCA(3, 2, 3)
 *       3
 *     LCA(NULL, 2, 3)
 *       NULL
 *
 * @author zk
 */
public class LowestCommonAncestorOfABinaryTree {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 左子树右子树都不为空，返回 root
        if (left != null && right != null)
            return root;

        // 左子树或者右子树为空，返回不为空的
        return left != null ? left : right;
    }

}
